package 二分查找;

import java.util.Arrays;

public class LeetCode611_有效三角形个数 {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        if(nums.length < 3) {
            return 0;
        }
        int ans = 0;
        int i = 0;
        while(nums[i] == 0) {
            if(i == nums.length-1) {
                return 0;
            }
            i++;
        }
        // a
        for(; i < nums.length; i++) {
            for(int j = i+1; j < nums.length; j++) {
                int left = j + 1, right = nums.length - 1, k = j;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] < nums[i] + nums[j]) {
                        k = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }

                }

                ans += k - j;
            }
        }
        return ans;
    }
}
